﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0189_FrequencySort : IAlgorithm
    {
        // 451. 根据字符出现频率排序

        // 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

        // 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

        // 提示:
        //  1 <= s.length <= 5 * 10^5
        //  s 由大小写英文字母和数字组成

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public string FrequencySort(string s)
        {
            var map = new Dictionary<char, int>();
            int maxFreq = 0;
            foreach (var c in s)
            {
                if (map.ContainsKey(c)) map[c]++;
                else map.Add(c, 1);
                maxFreq = Math.Max(maxFreq, map[c]);
            }

            var buckets = new StringBuilder[maxFreq + 1];
            for (int i = 0; i <= maxFreq; i++)
                buckets[i] = new StringBuilder();
            foreach (var pair in map)
                buckets[pair.Value].Append(pair.Key);

            StringBuilder sb = new StringBuilder();
            for (int i = maxFreq; i > 0; i--)
            {
                StringBuilder bucket = buckets[i];
                int size = bucket.Length;
                for (int j = 0; j < size; j++)
                    for (int k = 0; k < i; k++)
                        sb.Append(bucket[j]);
            }
            return sb.ToString();
        }
    }
}
